package com.example.lib5.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {
    public static void main(String[] args) {
        /*//将表达式（3+4）*5-6转为逆波兰表达式，如下,计算结果为29
        String suffixExpression = "30 4 + 5 * 6 -";
        //将逆波兰表达式加入到ArrayList中
        List<String> list = getListString(suffixExpression);
        //根据list来获取结果
        int calculate = getCalculate(list);
        System.out.println("计算结果为：" + calculate);*/

        //2
        //将字符串转为逆波兰表达式

        String expression = "15+((2+3)*4)-5";
        //将字符串转为逆波兰表达式
        List<String> list1 = toInfixExpressionList(expression);
        System.out.println("表达式添加到list的结果：" + list1.toString());
        List<String> list = parseSuffixExpressionList(list1);
        System.out.println("后缀表达式："+list.toString());
        System.out.println("后缀表达式的运算结果为："+getCalculate(list));

    }

    private static List<String> parseSuffixExpressionList(List<String> list) {
        //创建一个s2栈，因为s2栈是不需要pop出去的，且还要把结果反过来才是后缀表达式，所以用ArrayList来替换
        List<String> s2 = new ArrayList<>();
        //创建一个s1栈
        Stack<String> s1 = new Stack<>();

        //遍历中缀表达式的list
        for (String s : list) {
            //如果是数字的话，直接加入到s2
            if (s.matches("\\d+")) {
                s2.add(s);
            } else if (s.equals("(")) {
                //如果是（的话，就加入到s1
                s1.push(s);
            } else if (s.equals(")")) {
                //如果是右）的话就把s1.pop,直到匹配到（，再把（给pop出去
                while (!s1.peek().equals("(")) {
                    s2.add(s1.pop());
                }
                s1.pop();
            } else {
                //其他，就是符号，就要判断s1是否为空，如果为空就加到s1取，如果不为空，就判断优先级，优先级大就直接加入，如果不是就s1.pop,然后自己加入到s1中
                if (s1.size() != 0 && MyOperation.getValue(s) <= MyOperation.getValue(s1.peek())) {
                    s2.add(s1.pop());
                }
                s1.push(s);
            }
        }
        //遍历完之后，就要把s1逐步加入到s2中
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        return s2;
    }

    private static List<String> toInfixExpressionList(String expression) {
        List<String> list = new ArrayList<>();
        int i = 0;//表示遍历的那个索引
        char c = ' ';
        do {
            //如果是符号的话，就直接加入
            if (i < expression.length() && expression.charAt(i) < 48 || expression.charAt(i) > 57) {
                list.add(expression.charAt(i) + "");
                i++;
            } else {
                //如果不是符号的话，就要判断这个数字是几位数，要加入这个数字的完整数
                String str = "";
                while (i < expression.length() && expression.charAt(i) >= 48 && expression.charAt(i) <= 57) {
                    str += expression.charAt(i);
                    i++;
                }
                list.add(str);
            }

        } while (i < expression.length());
        return list;

    }

    private static List<String> getListString(String suffixExpression) {
        List<String> list = new ArrayList<>();
        //对字符串进行分割
        String[] s = suffixExpression.split(" ");
        //遍历字符串数组，加入到list中
        for (String value : s) {
            list.add(value);
        }
        return list;
    }

    private static int getCalculate(List<String> list) {
        //创建一个String类型的栈
        Stack<String> stack = new Stack<>();
        //根据是否为数字对list进行遍历，压入到栈中
        for (String s : list) {
            if (s.matches("\\d+")) {//匹配为多位数
                //如果为数字的话，就直接加入到栈中
                stack.push(s);
            } else {//如果不是的话，取出栈两个值，然后跟这个符号进行计算，压入到栈
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                if (s.equals("+")) {
                    res = num2 + num1;
                } else if (s.equals("-")) {
                    res = num2 - num1;
                } else if (s.equals("*")) {
                    res = num2 * num1;
                } else if (s.equals("/")) {
                    res = num2 / num1;
                } else {
                    throw new RuntimeException("运算符有错");
                }
                //把res入栈
                stack.push(String.valueOf(res));
            }
        }
        return Integer.parseInt(stack.pop());
    }


}

class MyOperation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getValue(String s) {
        int value = 0;
        switch (s) {
            case "+":
                value=ADD;
                break;
            case "-":
                value=SUB;
                break;
            case "*":
                value=MUL;
                break;
            case "/":
                value=DIV;
                break;
            default:
                break;
        }
        return value;
    }
}
